package alo.p10.work;

import alo.p10.CountingSort;
import alo.p10.HeapSort;

/**
 * @ClassName CheckWhoWinsTheElection
 * @Description 谁获得选举胜利
 * @Author Fanxc
 * @DATE 2021/3/12 14:33
 * @Version 1.0
 */
public class CheckWhoWinsTheElection {
    //双重循环
    int checkWhoWinsTheElection(int[] A,int n){
        int counter,max=0,candidate=0;
        for (int i = 0; i < n; i++) {
            candidate=A[i];
            counter=0;
            for (int j = i+1; j < n; j++) {
                if (A[i]==A[j]){
                    counter++;
                }
                if (counter>max){
                    max=counter;
                    candidate=A[i];
                }
            }
        }
        return candidate;
    }
    //排序后，再循环
    int checkWhoWinsTheElection2(int[] A,int n){
        int curCounter=0,maxCounter=0;
        int curCandidate=A[0],maxCandidate=curCandidate;
        new HeapSort().heapSort(A,0,n-1);
        for (int i = 0; i < n; i++) {
            if (A[i]==curCandidate){
                curCounter++;
            }else {
                curCandidate=A[i];
                curCounter=1;
            }
            if (curCounter>maxCounter){
                maxCandidate=curCandidate;
                maxCounter=curCounter;
            }
        }
        return maxCandidate;
    }
    //计数排序后，再查找
    int checkWhoWinsTheElection3(int[] A,int n){
        int[] B=new int[n];
        new CountingSort().countingSort(A,n,B,3);//假设候选的人数为3

        int curCounter=0,maxCounter=0;
        int curCandidate=B[0],maxCandidate=curCandidate;
        for (int i = 0; i < n; i++) {
            if (B[i]==curCandidate){
                curCounter++;
            }else {
                curCandidate=B[i];
                curCounter=1;
            }
            if (curCounter>maxCounter){
                maxCandidate=curCandidate;
                maxCounter=curCounter;
            }
        }
        return maxCandidate;
    }
}
